# GUID.py
# Version 2.1. 
#
# Copyright (C) 2003    Dr. Conan C. Albrecht <conan_albrechtATbyu.edu>
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation; either
# version 2.1 of the License, or (at your option) any later version.
#
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.    See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA    02111-1307    USA
from zoundry.base.util.locking import ZMutex



##################################################################################################
###     A globally-unique identifier made up of time and ip and 8 random digits: 40 characters wide
###    
###     A globally unique identifier that combines ip, time, and random bits.    Since the 
###     time is listed first, you can sort records by guid.    You can also extract the time 
###     and ip if needed.    
###         
###     GUIDs make wonderful database keys.    They require no access to the 
###     database (to get the max index number), they are extremely unique, and they sort 
###     automatically by time.     GUIDs prevent key clashes when merging
###     two databases together, combining data, or generating keys in distributed
###     systems.
###
###     There is an Internet Draft for UUIDs, but this module does not implement it.
###     If the draft catches on, perhaps I'll conform the module to it.
###


# Changelog
# Sometime, 1997         Created the Java version of GUID
#                                        Went through many versions in Java
# Sometime, 2002         Created the Python version of GUID, mirroring the Java version
# November 24, 2003    Changed Python version to be more pythonic, took out object and made just a module
# December 2, 2003     Fixed duplicating GUIDs.    Sometimes they duplicate if multiples are created
#                                        in the same millisecond (it checks the last 100 GUIDs now and has a larger random part)
# December 9, 2003     Fixed MAX_RANDOM, which was going over sys.maxint
#

import random
import socket
import sys
import time

# The size of the circular queue.    Larger sizes give more assurance for uniqueness.
# Smaller sizes take less memory and are a tiny bit faster
QUEUE_SIZE = 100


#############################
###     global module variables

MAX_RANDOM = sys.maxint # converted to hex goes to 8 chars (at least, in Python 2.3)
rand = random.Random()
ip = u"" #$NON-NLS-1$
lock = ZMutex(u"guidMTX") #$NON-NLS-1$
lastguid = u"" #$NON-NLS-1$
try:
    ip = socket.gethostbyname(socket.gethostname())
except (socket.gaierror): # if we don't have an ip, default to someting in the 10.x.x.x private range
    ip = u'10' #$NON-NLS-1$
    for i in range(3):
        ip += u'.' + str(rand.randrange(1, 254)) #$NON-NLS-1$
hexip = u"".join([u"%04x" % long(i) for i in ip.split(u'.')]) # leave space for ip v6 (65K in each sub) #$NON-NLS-1$ #$NON-NLS-2$ #$NON-NLS-3$


#######################################
###     A simple circular set
###     to ensure we don't duplicate
###     GUIDs in the same millisecond
    
class CircularSet:
    u'''A circular set.    A set that maxes at a given size, replacing the oldest element after maximum size.
         This implementation is NOT thread safe.    (generate() below is thread safe, though)
    ''' #$NON-NLS-1$
    def __init__(self):
        self.queue = []
        self.queue_map = {} # for efficiency, we keep a map of everything
        self.queueindex = 0

    def add(self, val):
        u'''Adds a value to the queue''' #$NON-NLS-1$
        # check to see if we have this value.    If so, throw an exception
        assert not self.queue_map.has_key(val), u'This value is already in the set!' #$NON-NLS-1$
        
        # add the new one to the list
        if len(self.queue) > self.queueindex:
            # first remove the previous key at this location
            del self.queue_map[self.queue[self.queueindex]]
            self.queue[self.queueindex] = val
        else:
            self.queue.append(val)
            
        # now add to the map for efficiency
        self.queue_map[val] = val
        
        # increment the queue index
        self.queueindex += 1
        if self.queueindex >= QUEUE_SIZE:
            self.queueindex = 0
            
queue = CircularSet()
    
#################################
###     Public module functions

def generate():
    u'''Generates a new guid''' #$NON-NLS-1$
    global lock, queue    # since we modify the module variable
    try:
        lock.acquire() # can't generate two guids at the same time
        while 1:
            parts = []
            # time part
            parts.append(u"%016x" % (long(time.time() * 1000))) #$NON-NLS-1$
            # ip part
            parts.append(hexip)
            # random part
            parts.append((u"%08x" % (rand.random() * MAX_RANDOM))[:8]) # limit to 8 chars, just in case maxint goes up in future Pythons #$NON-NLS-1$
            # put them all together
            guid = u"".join(parts) #$NON-NLS-1$
            try:
                queue.add(guid)    # throws the AssertionError if this GUID is a duplicate of the queue
                return guid
            except AssertionError: # signals we already have this GUID in the queue
                pass
    finally:
        lock.release()
        

def extract_time(guid):
    u'''Extracts the time portion out of the guid and returns the 
         number of seconds since the epoch as a float''' #$NON-NLS-1$
    return float(long(guid[0:16], 16)) / 1000


def extract_ip(guid):
    u'''Extracts the ip portion out of the guid and returns it
         as a string like 10.10.10.10''' #$NON-NLS-1$
    # there's probably a more elegant way to do this
    ip = u"" #$NON-NLS-1$
    index = 16
    while index < 32:
        if ip != u"": #$NON-NLS-1$
            ip += u"." #$NON-NLS-1$
        ip += str(int(guid[index: index + 4], 16))
        index += 4
    return ip


def extract_random(guid):
    u'''Extracts the random bits from the guid (returns the bits in decimal)''' #$NON-NLS-1$
    return int(guid[32:], 16)
